{
 "nbformat": 4,
 "nbformat_minor": 2,
 "metadata": {
  "language_info": {
   "name": "python",
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   }
  },
  "orig_nbformat": 2,
  "file_extension": ".py",
  "mimetype": "text/x-python",
  "name": "python",
  "npconvert_exporter": "python",
  "pygments_lexer": "ipython3",
  "version": 3
 },
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "给定一个二叉树，它的每个结点都存放着一个整数值。\n",
    "\n",
    "找出路径和等于给定数值的路径总数。\n",
    "\n",
    "路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。\n",
    "\n",
    "二叉树不超过1000个节点，且节点数值范围是 [-1000000,1000000] 的整数。\n",
    "\n",
    "```\n",
    "root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8\n",
    "\n",
    "      10\n",
    "     /  \\\n",
    "    5   -3\n",
    "   / \\    \\\n",
    "  3   2   11\n",
    " / \\   \\\n",
    "3  -2   1\n",
    "\n",
    "返回 3。和等于 8 的路径有:\n",
    "\n",
    "1.  5 -> 3\n",
    "2.  5 -> 2 -> 1\n",
    "3.  -3 -> 11\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "我写的代码，　test2 这个例子我重复把３计算了两次"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "        \n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, sum: int) -> int:\n",
    "\n",
    "        ans = 0\n",
    "\n",
    "        def helper(root, sum_, res):\n",
    "            nonlocal ans\n",
    "            if not root:\n",
    "                return\n",
    "            if sum_ - root.val == 0:\n",
    "                ans += 1\n",
    "\n",
    "            helper(root.left, sum_ - root.val, res + [root.val])\n",
    "            helper(root.right, sum_ - root.val, res + [root.val])\n",
    "            helper(root.left, sum, [])\n",
    "            helper(root.right, sum, [])\n",
    "\n",
    "        helper(root, sum, [])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "老师写的代码，在把左右节点做根的时候，不能又一起递归了"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, sum: int) -> int:\n",
    "\n",
    "        if not root:\n",
    "            return 0\n",
    "        ans = 0\n",
    "\n",
    "        def helper(root, sum_) -> int:\n",
    "            nonlocal ans\n",
    "            if not root:\n",
    "                return\n",
    "            if sum_ == root.val:\n",
    "                ans += 1\n",
    "\n",
    "            helper(root.left, sum_ - root.val)\n",
    "            helper(root.right, sum_ - root.val)\n",
    "            return ans\n",
    "\n",
    "        ans = helper(root, sum)\n",
    "        ans += self.pathSum(root.left, sum)\n",
    "        ans += self.pathSum(root.right, sum)\n",
    "\n",
    "        return ans"
   ]
  }
 ]
}